package com.note.feng.leetcode.algorithms.easy.tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class SixHundredFiftyThree {
    /**
     * 653 两数之和 IV - 输入 BST
     * 给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
     *
     * 示例 1：
     *
     * 输入: root = [5,3,6,2,4,null,7], k = 9
     * 输出: true
     * 示例 2：
     *
     * 输入: root = [5,3,6,2,4,null,7], k = 28
     * 输出: false
     *  
     * 提示:
     *
     * 二叉树的节点个数的范围是  [1, 104].
     * -104 <= Node.val <= 104
     * root 为二叉搜索树
     * -105 <= k <= 105
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/two-sum-iv-input-is-a-bst
     */
    /**
     * 解法：哈希
     * 先前序遍历，得到哈希表，在判断哈希表中是否包含 k - 当前元素 并且 当前元素 ！= k - 当前元素
     * 注意：依题意，二叉树中不存在重复元素
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        preorder(root, set);
        for (Integer integer : set){
            if(set.contains(k - integer) && k - integer != integer){
                return true;
            }
        }
        return false;
    }

    private void preorder(TreeNode node, Set<Integer> set){
        if(node == null){
            return;
        }
        preorder(node.left, set);
        set.add(node.val);
        preorder(node.right, set);
    }

    /**
     * 解法2：深度优先搜索 + 哈希表
     * 借助全局哈希表，递归判断是否包含 k - 当前节点值 ，
     * 若包含直接返回 true，
     * 否则，当前节点值 存入 set 中，继续遍历
     */
    Set<Integer> set1 = new HashSet<>();
    public boolean findTarget2(TreeNode root, int k) {
        if(root == null){
            return false;
        }
        if(set1.contains(k - root.val)){
            return true;
        }
        set1.add(root.val);
        return findTarget2(root.left, k) || findTarget2(root.right, k);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
